2479. Parentheses Balance

You are given a string consisting of parentheses ( ) and [ ]. A string of this type is said to be correct:

· if it is the empty string

· if A and B are correct, AB is correct,

· if A is correct, (A) and [A] is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input. The first line contains the number of test cases n. Each of the next n lines contains the string of parentheses ( ) and [ ].

Output. For each test case print in a separate line “Yes” if the expression is correct or “No” otherwise.

Sample input	Sample output
3 ([]) (([()]))) ([()[]()])()	Yes No Yes

SOLUTION

data structures - stack

Algorithm analysis

To solve the problem we’ll use stack of characters. We will process sequentially the symbols of the input string and:

· if the current character is an opening parenthesis (round or square), push it into the stack.

· if the current character is a closing bracket, then the corresponding opening parenthesis must be at the top of the stack. If this is not the case, or if the stack is empty, then the expression is not correct.

At the end of processing the correct line, the stack should be empty.

Example

Let’s simulate the stack for the string “( ( [ ] ) [ ] )”.

Algorithm realization

The input bracket expression we’ll read into an array stroka. Declare stack s that will be used in the problem solution.

char stroka[150];

stack<char> s;

Read the number of tests tests. For each input string stroka, calculate its length len. The flag will be set to 1 if the input parenthesized expression is not correct.

scanf("%d\n",&tests);

while(tests--)

{

gets(stroka); flag = 0;

Clear the stack s.

while(!s.empty()) s.pop();

Move along the symbols of input string stroka.

for(i = 0; i < strlen(stroka); i++)

{

Push the opening bracket into stack.

if ((stroka[i] == '(') || (stroka[i] == '[')) s.push(stroka[i]);

If current symbol stroka[i] is a closing bracket, pop the symbol from the top of the stack, that must be the corresponding opening bracket. If it is not, or if the stack is empty, set flag to 1.

else if (!s.empty() && ((stroka[i] == ')' && s.top() == '(') ||

(stroka[i] == ']' && s.top() == '['))) s.pop();

else flag = 1;

}

If the stack was not empty at the end of processing the line, then the input parenthesized expression is not correct.

if (!s.empty()) flag = 1;

Print the answer depending on the value of the variable flag.

if (flag) printf("No\n"); else printf("Yes\n");

}

Java realization

import java.util.*;

public class Main

{

static char rev(char c)

{

return (c == ')') ? '(' : '[';

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

String Line = con.nextLine();

while(tests-- > 0)

{

Line = con.nextLine();

Stack<Character> s = new Stack<Character>();

int Flag = 0;

for(int i = 0; i < Line.length(); i++)

{

if (Flag > 0) break;

if ((Line.charAt(i) == '(') || (Line.charAt(i) == '['))

s.push(Line.charAt(i));

if ((Line.charAt(i) == ')') || (Line.charAt(i) == ']'))

{

if (s.empty() || (s.peek() != rev(Line.charAt(i))))

Flag = 1;

else s.pop();

}

}

if (!s.empty()) Flag = 1;

if (Flag > 0) System.out.println("No");

else System.out.println("Yes");

}

}

}